package 算法;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.PriorityQueue;

/**
 * @author 挚爱之夕
 * @version 1.0
 * @implSpec 给定nums 数组和长度k
 * 求数组长度为k的序列中，最大值和最小值的最小差值
 * @since 2023 - 04 - 03 - 17:05
 */
public class _003_窗口最小差值 {
}
//两个队列
class Main3_1{
    //存下标
    static Deque<Integer> minQueue = new ArrayDeque<>();//LinkedList 超时了
    static Deque<Integer> maxQueue = new ArrayDeque<>();
    public static void main(String[] args) {
        int w = 3;
        int[] nums = {1, 3, 5, 10, 8, 7};
        int res = Integer.MAX_VALUE;

        for(int i = 0; i < nums.length; i++){
            //i 为新窗口右边界

            //处理最小
            if(!minQueue.isEmpty() && minQueue.peek() < i - w + 1){ //移出
                minQueue.pollFirst();
            }
            //如果min队列中比新加值nums[i]大，就不可能作为窗口最小值，移出
            //保证队头最小
            while(!minQueue.isEmpty() && nums[i] < nums[minQueue.peekLast()]){
                minQueue.pollLast();
            }
            minQueue.offerLast(i);


            //处理最大
            if(!maxQueue.isEmpty() && maxQueue.peek() < i - w + 1){
                maxQueue.pollFirst();
            }
            //如果max队列中比新加值nums[i]小，就不可能作为窗口最大值，移出
            while (!maxQueue.isEmpty() && nums[i] > nums[maxQueue.peekLast()]){
                maxQueue.pollLast();
            }
            maxQueue.offerLast(i);

            //窗口大小为 w
            if(i >= w - 1){
//                System.out.println(nums[maxQueue.peekFirst()] - nums[minQueue.peekFirst()]);
                res = Math.min(res, nums[maxQueue.peekFirst()] - nums[minQueue.peekFirst()]);
            }
        }
        System.out.println(res);
    }
}
//两个优先队列 (数据量大，可能超时)
class Main3_2{
    static PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    static PriorityQueue<Integer> maxHeap = new PriorityQueue<>((e1, e2) -> e2 - e1);
    static void remove(int num){
        minHeap.remove(num);
        maxHeap.remove(num);
    }
    static void offer(int num){
        minHeap.offer(num);
        maxHeap.offer(num);
    }
    public static void main(String[] args) {
        int k = 3;
        int[] nums = {1, 3, 5, 10, 8, 7};
        int res = Integer.MAX_VALUE;

        for(int i = 0; i < k ; i++){
            offer(nums[i]);
        }

        for(int i = 0; i + k <= nums.length; i++){
//            System.out.println(maxHeap.peek() - minHeap.peek());
            res = Math.min(res, maxHeap.peek() - minHeap.peek());
            remove(nums[i]);
            if(i + k < nums.length){
                offer(nums[i + k]);
            }
        }
        System.out.println(res);
    }
}
